|
In graph theory, the De Bruijn–Erdős theorem, proved by , states that, for every infinite graph and finite integer , can be colored by colors (with no two adjacent vertices having the same color) if and only if all of its finite subgraphs can be colored by colors. That is, every -critical graph (a graph that requires colors but for which all subgraphs require fewer colors) must have a finite number of vertices. The De Bruijn–Erdős theorem has several different proofs, all depending in some way on the axiom of choice. Its applications include extending the four-color theorem and Dilworth's theorem from finite graphs and partial orders to infinite ones, and reducing the Hadwiger–Nelson problem on the chromatic number of the plane to a problem about finite graphs. It may be generalized from finite numbers of colors to sets of colors whose cardinality is a strongly compact cardinal. ==Proofs== The original proof by De Bruijn used transfinite induction.〔 (p. 236).〕 provided the following very short proof, based on Tychonoff's compactness theorem in topology. Suppose that, for the given infinite graph , every finite subgraph is -colorable, and let be the space of all assignments of the colors to the vertices of (regardless of whether they form a valid coloring). Then may be viewed as a product space which by Tychonoff's theorem is compact. For each finite subgraph of , let be the subset of consisting of assignments of colors that validly color . Then the system of sets is a family of closed sets with the finite intersection property, so by compactness it has a nonempty intersection. Every member of this intersection is a valid coloring of .〔. Gottschalk states his proof more generally as a proof of the theorem of that generalizes the De Bruijn–Erdős theorem.〕 A different proof using Zorn's lemma was given by Lajos Pósa, and also in the 1951 Ph.D. thesis of Gabriel Andrew Dirac. If is an infinite graph in which every finite subgraph is -colorable, then by Zorn's lemma it is a subgraph of a maximal graph with the same property (one to which no more edges may be added without causing some finite subgraph to require more than colors). The binary relation of nonadjacency in is an equivalence relation and its equivalence classes provide a -coloring of . However, this proof is more difficult to generalize than the compactness proof.〔; . Jensen and Toft attribute to Gert Sabidussi the observation that Gottschalk's proof is easier to generalize. Soifer (pp. 238–239) gives the same proof via Zorn's lemma, rediscovered in 2005 by undergraduate student Dmytro Karabash.〕 The theorem can also be proved using ultrafilters〔.〕 or non-standard analysis.〔.〕 gives a proof for graphs with a countable number of vertices based on König's infinity lemma. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「De Bruijn–Erdős theorem (graph theory)」の詳細全文を読む スポンサード リンク
|